package basic;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created on 2019/9/18.
 */
public class LinkListTest {
    /*
        删除链表倒数第 n 个结点
        求链表的中间结点
*/
    public static void main(String[] args) {
        // 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
        HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
        m.put(3, 11);
        m.put(1, 12);
        m.put(5, 23);
        m.put(2, 22);

        m.put(3, 26);
        m.get(5);

        for (Map.Entry e : m.entrySet()) {
            System.out.println(e.getKey());
        }


        SingleLinkedList<Integer> linked = new SingleLinkedList<Integer>();
        for (int i = 0; i < 5; i++) {
            linked.addHead(i);
        }
        linked.display();
//        reverse(linked).display();

        //手动创建环
//        SingleLinkedList<Integer>.Node node = linked.find(2);
//        node.setNext(linked.getHead());
//        linked.display();
//        System.out.println(checkRing(linked));

        //创造另一个有序链表
        SingleLinkedList<Integer> linked2 = new SingleLinkedList<Integer>();
        for (int i = 0; i < 8; i = i + 2) {
            linked2.addHead(i);
        }
        linked2.display();
        mergeSortedLink(linked, linked2);

        linked.display();

    }

    //单链表反转
    public static SingleLinkedList<Integer> reverse(SingleLinkedList<Integer> linked){
        //1->2->3
        if (linked.getSize() < 1) {
            return linked;
        }else {
            SingleLinkedList<Integer>.Node pre = linked.getHead();
            SingleLinkedList<Integer>.Node cur = pre.getNext();
            SingleLinkedList<Integer>.Node temp;
            pre.setNext(null);
            while (cur != null) {
                temp = cur.getNext();
                cur.setNext(pre);
                pre = cur;
                cur = temp;
            }
            linked.setHead(pre);
        }
        return linked;
    }

    //        链表中环的检测
    public static boolean checkRing(SingleLinkedList<Integer> linked){
        SingleLinkedList<Integer>.Node one = linked.getHead();
        if(one == null) return false;
        SingleLinkedList<Integer>.Node two = one.getNext();
        while (two != null && two.getNext() !=null) {
            if (one.equals(two)) {
                return true;
            }else{
                one = one.getNext();
                two = two.getNext().getNext();
            }
        }
        return false;
    }

    //有序连表合并
    public static SingleLinkedList<Integer> mergeSortedLink(SingleLinkedList<Integer> linked, SingleLinkedList<Integer> linked2) {
        SingleLinkedList<Integer>.Node head1 = linked.getHead();
        SingleLinkedList<Integer>.Node head2 = linked2.getHead();
        linked.setHead(mergeTwoLists(head1, head2));
        linked.reCalcSize();
        return linked;
    }
    private static SingleLinkedList<Integer>.Node mergeTwoLists(SingleLinkedList<Integer>.Node l1, SingleLinkedList<Integer>.Node l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        SingleLinkedList<Integer>.Node head = null;
        if (l1.getData() > l2.getData()) {
            head = l1;
            head.setNext(mergeTwoLists(l1.getNext(), l2));
        } else {
            head = l2;
            head.setNext(mergeTwoLists(l1, l2.getNext()));
        }
        return head;
    }


}
